//MySort.hh
#ifndef MY_SORT_HH
#define MY_SORT_HH
#include <vector>
#include <algorithm>
#include <iostream>
namespace My_Code{
    using namespace std;
    template<typename T> void My_Sort(vector<T>& a)
    {
        int i,j;
        for(i = 0;i<a.size();i++)
        {
            for(j = i;j<a.size();j ++)
            {
                if(a[i] > a[j])
                {
                    swap(a[i],a[j]);
                }
            }
        }
    }
    template<typename T> void insertionsort(vector<T>& a)
    {
        int k;
        for(int p = 0;p <a.size();p++)
        {
            T temp = a[p];
            for(k = p;k > 0&&temp<a[k-1];k --)
            {
                a[k] = a[k-1];
                a[k-1] = temp;
            }
            }
    }
    template<typename T> void shellsort(vector<T>& a)
    {
        for(int gap = a.size()/2;gap > 0;gap /= 2)
        {
            for(int i = gap;i < a.size();i++)
            {
                T temp = a[i];
                int j= i;
                for(j;j >= gap && temp<=a[j-gap];j-=gap)
                a[j] = a[j-gap];
                a[i]=temp;
            }
        }
    }
    template<typename T>
    void mergesort(vector<T>&a)
    {
        vector<T> tempA(a.size());
        mergesort(a,tempA,0,a.size()-1);
    }

    template<typename T>
    void mergesort(vector<T>& a,vector<T>& tempA,int left,int right)
    {
        if(left < right)
        {
            int center = (left + right)/2;
            mergesort(a,tempA,left,center);
            mergesort(a,tempA,center+1,right);
            merge(a,tempA,left,center+1,right);
        }
    }
    template<typename T>
    void merge(vector<T>& a,vector<T>& b,int left,int center,int right)
    {
        int leftend = center - 1;
        int temppos = left;
        int numelement = right - left + 1;
        while(left<leftend && center<right)
        if(a[left]<a[center])
        b[temppos++]=a[left++];
        else
        b[temppos++]=a[center++];
        for(int i=0;i<numelement;i++,right--)
        a[right] = b[right];
    }
}
#endif